package t

import "fmt"

// 暴力改良匹配
func LongestPalindrome(s string) string {
	p1 := 0
	len := len(s)
	start := 0
	l := 0
	if len == 1 || s == ""{
		return s
	}
	for p1 < len && len-p1 > l{
		p2 := p1 + 1
		for p2 < len  {
			if s[p1] == s[p2] {
				kp1 := p1
				kp2 := p2
				for kp1 < kp2 {
					if s[kp1] == s[kp2] {
						kp1++
						kp2--
					}else {
						break
					}
				}
				if kp1 >= kp2 {
					tempLen := (p2-p1)+1
					if tempLen >= l {
						l = tempLen
						start = p1
					}
				}
			}
			p2++
		}
		p1++
	}
	sByte := []byte(s)
	if start == 0 && l == 0 {
		l = 1
	}
	res := string(sByte[start:(l+start)])
	return res
}

// 动态规划求解
func LongestPalindromeDp(s string) string {
	maxL := 1
	start := 0
	leng := len(s)
	dp := make([][]bool, leng)
	for i:=0; i<leng; i++ {
		dp[i] = make([]bool, leng)
	}
	for i:=0;i<leng ;i++  {
		dp[i][i] = true
	}
	for j:=1; j<leng; j++ {
		for i:=0; i<leng-1 && i < j ; i++ {
			if s[j] != s[i] {
				dp[i][j] = false
			}else {
				if j - i < 3 {
					dp[i][j] = true
				}else{
					dp[i][j] = dp[i+1][j-1]
				}
			}

			if dp[i][j] == true && j - i + 1 > maxL {
				maxL = j - i + 1
				start = i
			}
		}
	}
	fmt.Println(dp)
	fmt.Println(start, maxL)
	sByte := []byte(s)
	res := string(sByte[start:start+maxL])

	return res

}

func LongestPalindromeCenter(s string) string {
	len := len(s)
	left := 0
	right := 0
	l := 1
	maxS := 0
	maxL := 0

	for i:=0; i<len; i++ {
		left = i-1
		right = i+1
		for left >=0 && s[left] == s[i] {
			l++
			left--
		}
		for right < len && s[right] == s[i] {
			l++
			right++
		}
		for left >=0 && right < len && s[right] == s[left] {
			l = l + 2
			left--
			right++
		}
		if l > maxL {
			maxL = l
			maxS = left
		}
		l = 1
	}

	sByte := []byte(s)
	res := string(sByte[maxS+1:maxS+maxL+1])

	return res
}